package com.bwt.stack;

import java.util.Scanner;

public class SingleLinkedListStackDemo {
	public static void main(String[] args) {
		// 测试代码如下:
		// 先创建一个对象---》表示栈
		SingleLinkedListStack stack = new SingleLinkedListStack(5);
		String key = ""; // 空串
		boolean loop = true; // 控制是否退出菜单
		Scanner scanner = new Scanner(System.in);

		while (loop) {
			System.out.println("show:表示显示栈");
			System.out.println("exit:退出程序");
			System.out.println("push:表示添加数据到栈(入栈)");
			System.out.println("pop:表示从栈取出数据(出栈)");
			System.out.println("请输入你的选择:");
			key = scanner.next();
			switch (key) {
				case "show":
					stack.list();
					break;
				case "push":
					System.out.println("请输入一个数:");
					int value = scanner.nextInt();
					SingleLinkedList list = new SingleLinkedList(value);
					stack.push(list);
					break;
				case "pop":
					try {
						SingleLinkedList res = stack.pop();
						System.out.printf("取出的数据是%s\n", res.toString());
					} catch (Exception e) {
						System.out.println(e.getMessage());
					}
					break;
				case "exit":
					scanner.close();
					loop = false;
					break;
				default:
					break;
			}
		}
		System.out.println("程序退出！！！！");
	}
}

class SingleLinkedListStack {
	// 初始化一个头节点 不要动
	public SingleLinkedList head = new SingleLinkedList(-1);
	// 定义一个节点，代表栈顶所指节点
	public SingleLinkedList top = null;

	public int maxSize;

	public SingleLinkedListStack(int maxSize) {
		this.maxSize = maxSize;
	}

	public boolean isEmpty() {
		return top == null;
	}

	public boolean isFull() {
		SingleLinkedList temp = head.next;
		int count = 0;
		while (temp != null) {
			temp = temp.next;
			count++;
		}
		return count == maxSize;
	}

	//单链表实现栈 使用头插法效率更高
	public void push(SingleLinkedList node) {
		if (isFull()) {
			System.out.println("栈满, 不能添加数据~~");
			return;
		}
		node.next = head.next;
		head.next = node;
		top = node;
	}

	public SingleLinkedList pop() {
		if (isEmpty()) {
			System.out.println("栈空, 没有数据~~");
			return null;
		}
		SingleLinkedList tmp = head.next;
		head.next = tmp.next;
		top = head.next;
		return tmp;
	}

	public void list() {
		if (isEmpty()) {
			System.out.println("链表为空！！！");
			return;
		}
		SingleLinkedList temp = head.next;
		while (temp != null) {
			System.out.println(temp);
			temp = temp.next;
		}
	}

	//单链表实现栈 把节点添加到链表的最后
	/*
	public void push(SingleLinkedList node) {
		if (isFull()) {
			System.out.println("栈满, 不能添加数据~~");
			return;
		}
		SingleLinkedList temp = head;
		while (temp.next != null) {
			temp = temp.next;
		}
		//退出循环时, temp 就指向了链表的最后一个节点
		temp.next = node;
		top = node;
	}
	*/

	// 删除节点从单向链表实现的栈中，即出栈
	/*public SingleLinkedList pop() {
		if (isEmpty()) {
			System.out.println("栈空, 没有数据~~");
			return null;
		}

		SingleLinkedList tmp = top;
		SingleLinkedList h = head;
		while (true) {
			if (h.next == top) {
				break;
			}
			h = h.next;
		}
		h.next = top.next;
		top = h;
		return tmp;
	}*/

/*	public void list() {
		if (isEmpty()) {
			System.out.println("链表为空！！！");
			return;
		}
		SingleLinkedList reverseList = getReverseList(head);
		SingleLinkedList temp = reverseList.next;
		while (temp != null) {
			System.out.println(temp);
			temp = temp.next;
		}
		getReverseList(head);
	}*/

	//获取反转的链表
	public SingleLinkedList getReverseList(SingleLinkedList head) {
		if (head.next == null || head.next.next == null) {
			return head;
		}
		SingleLinkedList cur = head.next;
		SingleLinkedList next = null;
		SingleLinkedList reversList = new SingleLinkedList(-1);
		while (cur != null) {
			next = cur.next;
			cur.next = reversList.next;
			reversList.next = cur;
			cur = next;
		}
		head.next = reversList.next;
		return reversList;
	}
}

class SingleLinkedList {
	public int val;
	public SingleLinkedList next;

	public SingleLinkedList(int val) {
		this.val = val;
	}

	@Override
	public String toString() {
		return "SingleLinkedList{" +
				"val=" + val +
				'}';
	}
}
